var numbers = [];
$(document).on("pagecreate", function(event) {
	if ($("#size") && $("#method") && $("#time") && $("#mumbers")&& $("#valid")) {
		document.getElementById("size").value = 1000;
		setSize();
	}
});

function setSize() {
	var method = document.getElementById("method");
	method.selectedIndex = 0;
	var size = parseInt(document.getElementById("size").value);
	method.options[1].disabled = size > 25000;
	method.options[2].disabled = size > 25000;
	method.options[3].disabled = size > 25000;
	numbers = [];
	var startTime = new Date().getTime();
	for (var i = 1; i <= size; ++i) {
		numbers.push(i);
	}
	shuffle(numbers);
	var diff = new Date().getTime() - startTime;
	document.getElementById("time").innerHTML = "It took " + diff + "ms to shuffle";
	document.getElementById("numbers").innerHTML = size > 10000 ? "" : numbers.join(", ");
	document.getElementById("valid").innerHTML = "Sorted = " + isSorted(numbers);
}

function swap(array, i, j) {
	var t = array[i];
	array[i] = array[j];
	array[j] = t;
}

function shuffle(array) {
	var i = array.length;
	while (i--) {
		var r = (Math.random() * i) | 0;
		swap(array, r, i);
	}
}

function sort() {
	var startTime = new Date().getTime();
	var method = document.getElementById("method").value;
	switch (method) {
	case "bubble":
		bubbleSort(numbers);
		break;
	case "insert":
		insertionSort(numbers);
		break;
	case "select":
		selectionSort(numbers);
		break;
	case "quick":
		quickSort(numbers, 0, numbers.length - 1);
		break;
	case "merge":
		mergeSort(numbers, 0, numbers.length - 1);
		break;
	case "heap":
		heapSort(numbers);
		break;
	case "internal":
		numbers.sort(function(a, b) {
			return a - b;
		});
		break;
	}
	var diff = new Date().getTime() - startTime;
	document.getElementById("time").innerHTML = method + " sort took " + diff + "ms";
	document.getElementById("numbers").innerHTML = numbers.length > 10000 ? "" : numbers.join(", ");
	document.getElementById("valid").innerHTML = "Sorted = " + isSorted(numbers);
}

function isSorted(array) {
	for (var i = 1; i < array.length; ++i) {
		if (array[i - 1] > array[i]) {
			return false;
		}
	}
	return true;
}

function bubbleSort(array) {
	var n = array.length;
	do {
		var t = 0;
		for (var i = 1; i < n; ++i) {
			if (array[i - 1] > array[i]) {
				swap(array, i - 1, i);
				t = i;
			}
		}
		n = t;
	} while (n !== 0);
}

function insertionSort(array) {
	for (var i = 1; i < array.length; ++i) {
		var x = array[i];
		for (var j = i; j > 0 && array[j - 1] > x; --j) {
			array[j] = array[j - 1];
		}
		array[j] = x;
	}
}

function selectionSort(array) {
	for (var i = 0; i < array.length - 1; i++) {
		var mi = i;
		for (var j = i + 1; j < array.length; j++) {
			if (array[j] < array[mi]) {
				mi = j;
			}
		}
		if (i !== mi) {
			swap(array, i, mi);
		}
	}
}

function quickSort(array, left, right) {
	if (left >= right) {
		return;
	}
	var pivot = partition(array, left, right);
	if (pivot - left < right - pivot) {
		quickSort(array, left, pivot - 1);
		quickSort(array, pivot + 1, right);
	} else {
		quickSort(array, pivot + 1, right);
		quickSort(array, left, pivot - 1);
	}
}

function partition(array, left, right) {
	var pivotIndex = ~~(left + (right - left) / 2);
	var pivotValue = array[pivotIndex];
	swap(array, pivotIndex, right);
	pivotIndex = left;
	for (var i = left; i < right; ++i) {
		if (array[i] < pivotValue) {
			swap(array, pivotIndex, i);
			++pivotIndex;
		}
	}
	swap(array, pivotIndex, right);
	return pivotIndex;
}

function mergeSort(array, left, right) {
	if (left === right) {
		return;
	}
	var mid = ~~(left + (right - left) / 2);
	mergeSort(array, left, mid);
	mergeSort(array, mid + 1, right);
	merge(array, left, mid, right);
}

function merge(array, left, mid, right) {
	var leftArray = array.slice(left, mid + 1);
	var rightArray = array.slice(mid + 1, right + 1);
	var l = 0;
	var r = 0;
	for (var i = left; i <= right; ++i) {
		if (l == leftArray.length) {
			array[i] = rightArray[r++];
		} else if (r == rightArray.length) {
			array[i] = leftArray[l++];
		} else if (leftArray[l] < rightArray[r]) {
			array[i] = leftArray[l++];
		} else {
			array[i] = rightArray[r++];
		}
	}
}

function heapSort(array) {
	var i;
	for (i = ~~(array.length / 2 - 1); i >= 0; --i) {
		siftDown(array, i, array.length);
	}
	for (i = array.length - 1; i > 0; --i) {
		swap(array, 0, i);
		siftDown(array, 0, i - 1);
	}
}

function siftDown(array, root, bottom) {
	var parent = root;
	var child;
	while (2 * parent <= bottom) {
		if (2 * parent == bottom) {
			child = 2 * parent;
		} else if (array[parent * 2] > array[parent * 2 + 1]) {
			child = 2 * parent;
		} else {
			child = 2 * parent + 1;
		}
		if (array[parent] < array[child]) {
			swap (array, parent, child);
			parent = child;
		}
		else {
			break;
		}
	}
}
